home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 October: Mac OS SDK / Dev.CD Oct 96 SDK / Dev.CD Oct 96 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc Source Code / Utilities / LinkList.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-22  |  16.1 KB  |  666 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        LinkList.cpp
  3.  
  4.     Contains:    Primitive linked list class
  5.  
  6.     Owned by:    Richard Rodseth, Jens Alfke
  7.  
  8.     Copyright:    © 1993 - 1995 by Apple Computer, Inc., all rights reserved.
  9.  
  10. */
  11.  
  12. #ifndef _LINKLIST_
  13. #include "LinkList.h"
  14. #endif
  15.  
  16. #ifndef _EXCEPT_
  17. #include "Except.h"
  18. #endif
  19.  
  20. #ifndef __ERRORS__
  21. #include <Errors.h>
  22. #endif
  23.  
  24. #ifndef _ODDEBUG_
  25. #include "ODDebug.h"
  26. #endif
  27.  
  28. #ifndef _UTILERRS_
  29. #include "UtilErrs.h"
  30. #endif
  31.  
  32. #pragma segment ODLinkedList
  33.  
  34. //==============================================================================
  35. // Constants
  36. //==============================================================================
  37.  
  38. //==============================================================================
  39. // Scalar Types
  40. //==============================================================================
  41.  
  42. //==============================================================================
  43. // Local Classes
  44. //==============================================================================
  45.  
  46. //==============================================================================
  47. // Global Variables
  48. //==============================================================================
  49.  
  50. //==============================================================================
  51. // Function Prototype
  52. //==============================================================================
  53.  
  54.  
  55. //==============================================================================
  56. // Link
  57. //==============================================================================
  58.  
  59.  
  60.  
  61. // Many of the simple link methods are inlines; see List.h for implementations.
  62.  
  63.  
  64. //------------------------------------------------------------------------------
  65. // Link::Link
  66. //
  67. // Constructor for Link
  68. //------------------------------------------------------------------------------
  69.  
  70. Link::Link()                            
  71. { 
  72.     fNext = kODNULL; 
  73.     fPrevious = kODNULL;
  74. }
  75.  
  76. //------------------------------------------------------------------------------
  77. // Link::Link
  78. //
  79. // Constructor for Link
  80. //------------------------------------------------------------------------------
  81.  
  82. Link::Link(Link* next, Link* previous)                            
  83. { 
  84.     fNext = next; 
  85.     fPrevious = previous;
  86. }
  87.  
  88. //------------------------------------------------------------------------------
  89. // Link::Link
  90. //
  91. // Copy constructor for Link
  92. //------------------------------------------------------------------------------
  93.  
  94. Link::Link( const Link &link )                            
  95. { 
  96.     fNext = link.fNext; 
  97.     fPrevious = link.fPrevious;
  98. }
  99.  
  100. //------------------------------------------------------------------------------
  101. // Link::Link
  102. //
  103. // Destructor for Link
  104. //------------------------------------------------------------------------------
  105.  
  106. Link::~Link()                                            
  107. {
  108. }
  109.  
  110. //------------------------------------------------------------------------------
  111. // Link::Remove
  112. //
  113. // Remove a link from its list (if any). DO NOT call this directly if there are
  114. // any iterators active on the list; use LinkedList::Remove instead.
  115. //------------------------------------------------------------------------------
  116.  
  117. void    Link::Remove( )
  118. {
  119.     if( fPrevious )
  120.         fPrevious->SetNext(fNext);
  121.     if( fNext )
  122.         fNext->SetPrevious(fPrevious);
  123.     fNext = kODNULL;
  124.     fPrevious = kODNULL;
  125. }
  126.  
  127. //------------------------------------------------------------------------------
  128. // Link::AddBefore
  129. //
  130. // Add a link to a list before another link. It must not already be on any list.
  131. // DO NOT call this directly if there are any iterators active on the list;
  132. // use LinkedList::Remove instead.
  133. //------------------------------------------------------------------------------
  134.  
  135. void    Link::AddBefore( Link *link )
  136. {
  137.     ASSERT(link!=kODNULL,paramErr);
  138.     WASSERT(fNext==kODNULL);
  139.     WASSERT(fPrevious==kODNULL);
  140.     fNext = link;
  141.     fPrevious = link->GetPrevious();
  142.     fPrevious->SetNext(this);
  143.     fNext->SetPrevious(this);
  144. }
  145.  
  146. //------------------------------------------------------------------------------
  147. // Link::AddAfter
  148. //
  149. // Add a link to a list after another link. It must not already be on any list.
  150. // DO NOT call this directly if there are any iterators active on the list;
  151. // use LinkedList::Remove instead.
  152. //------------------------------------------------------------------------------
  153.  
  154. void    Link::AddAfter( Link *link )
  155. {
  156.     ASSERT(link!=kODNULL,paramErr);
  157.     WASSERT(fNext==kODNULL);
  158.     WASSERT(fPrevious==kODNULL);
  159.     fPrevious = link;
  160.     fNext = link->GetNext();
  161.     fPrevious->SetNext(this);
  162.     fNext->SetPrevious(this);
  163. }
  164.  
  165. //======================================================================================
  166. // Class LinkedList
  167. //======================================================================================
  168.  
  169. //------------------------------------------------------------------------------
  170. // LinkedList::LinkedList
  171. //
  172. // Constructor for LinkedList
  173. //------------------------------------------------------------------------------
  174.  
  175. LinkedList::LinkedList()
  176.     :fSentinel(&fSentinel,&fSentinel),
  177.      fSeed(0)
  178. {
  179. }
  180.  
  181. //------------------------------------------------------------------------------
  182. // LinkedList::~LinkedList
  183. //
  184. // Destructor for LinkedList
  185. //------------------------------------------------------------------------------
  186.  
  187. LinkedList::~LinkedList()
  188. {
  189.     // The list does NOT delete all its links!
  190. }
  191.  
  192. //------------------------------------------------------------------------------
  193. // LinkedList::IsEmpty
  194. //
  195. // Description
  196. //------------------------------------------------------------------------------
  197.  
  198. ODBoolean LinkedList::IsEmpty() const
  199. {
  200.     return this->IsSentinel( fSentinel.GetNext() );
  201. }
  202.  
  203. //------------------------------------------------------------------------------
  204. // LinkedList::Count
  205. //
  206. // Description
  207. //------------------------------------------------------------------------------
  208.  
  209. ODULong LinkedList::Count() const
  210. {
  211.     Link* l = fSentinel.GetNext();
  212.     ODULong count = 0;
  213.     while (this->NotSentinel(l))
  214.     {
  215.         count++;
  216.         l = l->GetNext();
  217.         ASSERT(l!=kODNULL,kODErrAssertionFailed);
  218.     }
  219.     return count;
  220. }
  221.  
  222. //------------------------------------------------------------------------------
  223. // LinkedList::Includes
  224. //
  225. // Does the list include a particular link?
  226. //------------------------------------------------------------------------------
  227.  
  228. ODBoolean LinkedList::Includes( const Link *link ) const
  229. {
  230.     Link* l = fSentinel.GetNext();
  231.     while (this->NotSentinel(l))
  232.     {
  233.         if( l == link )
  234.             return kODTrue;
  235.         else
  236.             l = l->GetNext();
  237.     }
  238.     return kODFalse;
  239. }
  240.  
  241. //------------------------------------------------------------------------------
  242. // LinkedList::DeleteAllLinks
  243. //
  244. // Description
  245. //------------------------------------------------------------------------------
  246.  
  247. void    LinkedList::DeleteAllLinks()
  248. {
  249.  
  250.     Link* l = fSentinel.GetNext();
  251.     Link* n = l;
  252.     while (this->NotSentinel(n))
  253.     {
  254.         n = l->GetNext();
  255.         delete l;    
  256.         l = n;
  257.     }
  258.     fSentinel.SetNext(&fSentinel);
  259.     fSentinel.SetPrevious(&fSentinel);
  260.     fSeed++;
  261. }
  262.  
  263. //------------------------------------------------------------------------------
  264. // LinkedList::RemoveAll
  265. //
  266. // Description
  267. //------------------------------------------------------------------------------
  268.  
  269. void    LinkedList::RemoveAll()
  270. {
  271.  
  272.     Link* l = fSentinel.GetNext();
  273.     Link* n = l;
  274.     while (this->NotSentinel(l))
  275.     {
  276.         n = l->GetNext();
  277.         l->SetNext(kODNULL);
  278.         l->SetPrevious(kODNULL);
  279.         l = n;
  280.     }
  281.     fSentinel.SetNext(&fSentinel);
  282.     fSentinel.SetPrevious(&fSentinel);
  283. }
  284.  
  285. //------------------------------------------------------------------------------
  286. // LinkedList::Remove
  287. //
  288. // Description
  289. //------------------------------------------------------------------------------
  290.  
  291. void    LinkedList::Remove(Link& aLink)
  292. {
  293.     fSeed++;
  294.     aLink.Remove();
  295. }
  296.  
  297. //------------------------------------------------------------------------------
  298. // LinkedList::RemoveFirst
  299. //
  300. // Description
  301. //------------------------------------------------------------------------------
  302.  
  303. Link* LinkedList::RemoveFirst()
  304. {
  305.     Link* old = fSentinel.GetNext();
  306.     if (this->NotSentinel(old))
  307.     {
  308.         fSeed++;
  309.         old->Remove();
  310.         return old;
  311.     }
  312.     else
  313.     {
  314.         return kODNULL;
  315.     }
  316. }
  317.  
  318. //------------------------------------------------------------------------------
  319. // LinkedList::RemoveLast
  320. //
  321. // Description
  322. //------------------------------------------------------------------------------
  323.  
  324. Link* LinkedList::RemoveLast()
  325. {
  326.     Link* old = fSentinel.GetPrevious();
  327.     if (this->NotSentinel(old))
  328.     {
  329.         fSeed++;
  330.         old->Remove();
  331.         return old;
  332.     }
  333.     else
  334.     {
  335.         return kODNULL;
  336.     }
  337. }
  338.  
  339. //------------------------------------------------------------------------------
  340. // LinkedList::AddFirst
  341. //
  342. // Description
  343. //------------------------------------------------------------------------------
  344.  
  345. void    LinkedList::AddFirst(Link* link)
  346. {
  347.     link->AddAfter(this->GetSentinel());
  348.     fSeed++;
  349. }
  350.  
  351. //------------------------------------------------------------------------------
  352. // LinkedList::AddLast( Link )
  353. //
  354. // Description
  355. //------------------------------------------------------------------------------
  356.  
  357. void    LinkedList::AddLast(Link* link)
  358. {
  359.     link->AddBefore(this->GetSentinel());
  360.     fSeed++;
  361. }
  362.  
  363. //------------------------------------------------------------------------------
  364. // LinkedList::AddLast( LinkedList )
  365. //
  366. // Append contents of another list to my end. (Other list becomes empty.)
  367. //------------------------------------------------------------------------------
  368.  
  369. void    LinkedList::AddLast( LinkedList &list )
  370. {
  371.     if( !list.IsEmpty() ) {
  372.         Link *myLast = fSentinel.GetPrevious();
  373.         Link *itsFirst = list.First();
  374.         myLast->SetNext(itsFirst);
  375.         itsFirst->SetPrevious(myLast);
  376.         
  377.         Link *itsLast = list.Last();
  378.         itsLast->SetNext(this->GetSentinel());
  379.         fSentinel.SetPrevious(itsLast);
  380.         
  381.         list.fSentinel.SetNext(this->GetSentinel());
  382.         list.fSentinel.SetPrevious(this->GetSentinel());
  383.  
  384.         fSeed++;
  385.         list.fSeed++;
  386.     }
  387. }
  388.  
  389. //------------------------------------------------------------------------------
  390. // LinkedList::AddLastUnique( LinkedList )
  391. //
  392. // Append contents of another list (w/o duplication) to my end.
  393. //------------------------------------------------------------------------------
  394.  
  395. void    LinkedList::AddLastUnique( LinkedList &list )
  396. {
  397.     for( Link *link = fSentinel.GetNext(); this->NotSentinel(link); link=link->GetNext() )
  398.         if( list.Includes(link) )
  399.             list.Remove(*link);
  400.     this->AddLast(list);
  401. }
  402.  
  403. //------------------------------------------------------------------------------
  404. // LinkedList::AddBefore
  405. //
  406. // Description
  407. //------------------------------------------------------------------------------
  408.  
  409. void LinkedList::AddBefore(Link& existing, Link* link)
  410. {
  411.     link->AddBefore(&existing);
  412.     fSeed++;
  413. }
  414.  
  415. //------------------------------------------------------------------------------
  416. // LinkedList::AddAfter
  417. //
  418. // Description
  419. //------------------------------------------------------------------------------
  420.  
  421. void LinkedList::AddAfter(Link& existing, Link* link)
  422. {
  423.     link->AddAfter(&existing);
  424.     fSeed++;
  425. }
  426.  
  427. //------------------------------------------------------------------------------
  428. // LinkedList::After
  429. //
  430. // Description
  431. //------------------------------------------------------------------------------
  432.  
  433. Link* LinkedList::After(const Link& link) const
  434. {
  435.     Link *next = link.GetNext();
  436.     if( this->IsSentinel(next) )
  437.         return kODNULL;
  438.     else
  439.         return next;
  440. }
  441.  
  442. //------------------------------------------------------------------------------
  443. // LinkedList::Before
  444. //
  445. // Description
  446. //------------------------------------------------------------------------------
  447.  
  448. Link* LinkedList::Before(const Link& link) const
  449. {
  450.     Link *prev = link.GetPrevious();
  451.     if( this->IsSentinel(prev) )
  452.         return kODNULL;
  453.     else
  454.         return prev;
  455. }
  456.  
  457. //------------------------------------------------------------------------------
  458. // LinkedList::First
  459. //
  460. // Description
  461. //------------------------------------------------------------------------------
  462.  
  463. Link*    LinkedList::First()  const
  464. {
  465.     return this->NotSentinel(fSentinel.GetNext()) ? fSentinel.GetNext() : (Link*) kODNULL;
  466. }
  467.  
  468. //------------------------------------------------------------------------------
  469. // LinkedList::Last
  470. //
  471. // Description
  472. //------------------------------------------------------------------------------
  473.  
  474. Link* LinkedList::Last() const
  475. {
  476.     return this->NotSentinel(fSentinel.GetPrevious()) ? fSentinel.GetPrevious() : (Link*) kODNULL;
  477. }
  478.  
  479.  
  480. //======================================================================================
  481. // Class LinkedListIterator
  482. //======================================================================================
  483.  
  484. //------------------------------------------------------------------------------
  485. // LinkedListIterator::LinkedListIterator
  486. //
  487. // Constructor for LinkedListIterator
  488. //------------------------------------------------------------------------------
  489.  
  490. LinkedListIterator::LinkedListIterator(LinkedList* list)
  491. {
  492.     fList = list;
  493.     fCurrent = kODNULL;
  494.     fNext = kODNULL;
  495.     fPrevious = kODNULL;
  496.     fSentinel = &list->fSentinel;
  497.     fSeed = fList->fSeed;    
  498. }
  499.  
  500. //------------------------------------------------------------------------------
  501. // LinkedListIterator::~LinkedListIterator
  502. //
  503. // Destructor for LinkedListIterator
  504. //------------------------------------------------------------------------------
  505.  
  506. LinkedListIterator::~LinkedListIterator()
  507. {
  508. }
  509.  
  510. //------------------------------------------------------------------------------
  511. // LinkedListIterator::First
  512. //
  513. // Description
  514. //------------------------------------------------------------------------------
  515.  
  516. Link* LinkedListIterator::First()
  517. {
  518.     if (fList == kODNULL)
  519.         return kODNULL;
  520.         
  521.     if (fSeed != fList->fSeed)
  522.         THROW(kODErrIteratorOutOfSync);
  523.         
  524.     fCurrent = fList->First();
  525.     if (fCurrent == fSentinel)
  526.         fCurrent = kODNULL;
  527.     return fCurrent;
  528. }
  529.  
  530. //------------------------------------------------------------------------------
  531. // LinkedListIterator::Next
  532. //
  533. // Description
  534. //------------------------------------------------------------------------------
  535.  
  536. Link* LinkedListIterator::Next()
  537. {
  538.     if (fList == kODNULL)
  539.         return kODNULL;
  540.  
  541.     if (fSeed != fList->fSeed)
  542.         THROW(kODErrIteratorOutOfSync);
  543.  
  544.     if (fCurrent == kODNULL)
  545.     {
  546.         if ((fNext == kODNULL) && (fPrevious == kODNULL))    // Just starting out
  547.         {
  548.             return this->First();
  549.         }
  550.         else    // Just deleted
  551.         {
  552.             fCurrent = fNext;
  553.             fPrevious = kODNULL;
  554.             fNext = kODNULL;
  555.         }
  556.     }
  557.     else
  558.         fCurrent = fCurrent->GetNext();
  559.     
  560.     if (fCurrent == fSentinel)
  561.         fCurrent = kODNULL;
  562.     return fCurrent;
  563. }
  564.  
  565. //------------------------------------------------------------------------------
  566. // LinkedListIterator::Last
  567. //
  568. // Description
  569. //------------------------------------------------------------------------------
  570.  
  571. Link* LinkedListIterator::Last()
  572. {
  573.     if (fList == kODNULL)
  574.         return kODNULL;
  575.  
  576.     if (fSeed != fList->fSeed)
  577.         THROW(kODErrIteratorOutOfSync);
  578.  
  579.     fCurrent = fList->Last();
  580.     if (fCurrent == fSentinel)
  581.         fCurrent = kODNULL;
  582.     return fCurrent;
  583. }
  584.  
  585. //------------------------------------------------------------------------------
  586. // LinkedListIterator::Previous
  587. //
  588. // Description
  589. //------------------------------------------------------------------------------
  590.  
  591. Link* LinkedListIterator::Previous()
  592. {
  593.     if (fList == kODNULL)
  594.         return kODNULL;
  595.  
  596.     if (fSeed != fList->fSeed)
  597.         THROW(kODErrIteratorOutOfSync);
  598.  
  599.     if (fCurrent == kODNULL)
  600.     {
  601.         if ((fNext == kODNULL) && (fPrevious == kODNULL))    // Just starting out
  602.         {
  603.             return this->Last();
  604.         }
  605.         else    // Just deleted
  606.         {
  607.             fCurrent = fPrevious;
  608.             fPrevious = kODNULL;
  609.             fNext = kODNULL;
  610.         }
  611.     }
  612.     else
  613.         fCurrent = fCurrent->GetPrevious();
  614.  
  615.     if (fCurrent == fSentinel)
  616.         fCurrent = kODNULL;
  617.     return fCurrent;
  618. }
  619.  
  620. //------------------------------------------------------------------------------
  621. // LinkedListIterator::Current
  622. //
  623. // Description
  624. //------------------------------------------------------------------------------
  625.  
  626. Link* LinkedListIterator::Current()
  627. {
  628.     return fCurrent;
  629. }
  630.  
  631. //------------------------------------------------------------------------------
  632. // LinkedListIterator::IsNotComplete
  633. //
  634. // Description
  635. //------------------------------------------------------------------------------
  636.  
  637. ODBoolean LinkedListIterator::IsNotComplete()
  638. {
  639.     return (fCurrent != kODNULL);
  640. }
  641.  
  642. //------------------------------------------------------------------------------
  643. // LinkedListIterator::RemoveCurrent
  644. //
  645. // Description
  646. //------------------------------------------------------------------------------
  647.  
  648. void  LinkedListIterator::RemoveCurrent()
  649. {
  650.     if (fList == kODNULL)
  651.         return;
  652.         
  653.     if (fSeed != fList->fSeed)
  654.         THROW(kODErrIteratorOutOfSync);
  655.          
  656.     if (fCurrent != kODNULL)
  657.     {
  658.         fNext = fCurrent->GetNext();
  659.         fPrevious = fCurrent->GetPrevious();
  660.             
  661.         fList->Remove(*fCurrent);
  662.         fCurrent = kODNULL;
  663.         fSeed = fList->fSeed;
  664.     }
  665. }
  666.